package algorithm.sort.common;

/**
 * @author bingo
 * @create 2018-02-23 14:25
 **/
public class MaxHeap {

    public MaxHeap() {

    }

    public Integer[] data;

    public Integer count;

    public Integer size;

    public MaxHeap(int size){
        this.size=size;
        count=0;
        this.data = new Integer[size+1];
    }

    public void insert(int i){
        data[count+1]=i; //data[0]有值

        count++;

        shiftUp(count);

        }
    private void shiftUp(Integer k) {
        while(k > 1 && data[k] > data[k/2]){
            int temp = data[k/2];
            data[k/2]=data[k];
            data[k]=temp;
            k/=2;
        }

    }
    public int push(){
        int number = data[1];
        int temp = data[1];
        data[1]=data[count];
        data[count]=temp;
        count--;
        shiftDown(1);
       return number;

    }

    private void shiftDown(int k) {
        while(2*k <= count){
            int j=2*k;
            if(j+1 <= count&&data[j+1]>data[j]){
                j=j+1;
            }
            if(data[k]>=data[j]){
                break;
            }
            int temp = data[k];
            data[k]=data[j];
            data[j]=temp;
             k=j;
             }
         }


    public Integer size() {
        return size;
    }





    public static void main(String[] args) {
        MaxHeap maxHeap = new MaxHeap(50);

        for(int i=0;i<50;i++){
        maxHeap.insert(i);
    }

        for(int i=0;i<50;i++){
        int n= maxHeap.push();
        System.out.print(n+",");

    }

}


}


